/*
题目描述：删除链表中重复的节点

 */
public class E18_2 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next.next = new ListNode(5);

        deleteDuplication(head);

        PrintListNode(head);
    }

    public static ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        ListNode preNode = null;
        ListNode pNode = pHead;
        while(pNode != null){
            ListNode pNext = pNode.next;
            boolean needDelete = false;
            if(pNext != null && pNext.value == pNode.value){
                needDelete = true;
            }
            if(!needDelete){
                preNode = pNode;
                pNode = pNode.next;
            }
            //如果需要删除，移动pNext指向一个非重复节点
            else{
                int value = pNode.value;
                ListNode pToBeDel = pNode;
                while(pToBeDel != null && pToBeDel.value == value){
                    pNext = pToBeDel.next;
                    pToBeDel = pNext;
                }
                if(preNode == null){
                    pHead = pNext;
                }
                else{
                    preNode.next = pNext;
                }
                pNode = pNext;
            }
        }
        return pHead;
    }

    public static void PrintListNode(ListNode pListHead){
        ListNode node = pListHead;
        while(node != null){
            if(node.next == null){
                System.out.print(node.value);
            }
            else{
                System.out.print(node.value + "->");
            }
            node = node.next;
        }
    }
}

//class ListNode{
//    int value;
//    ListNode next;
//    ListNode(int value){
//        this.value = value;
//    }
//}
/*
1->2->5
 */